ATM network planning involves designing a network equipped to satisfy all customers' traffic requirements, which may include the voice, data, image and video payloads. There are many issues to be considered in network planning. One well-known aspect of the planning process is the determination of the quantity, location and configuration of network access equipment required for the ingress and egress of customer traffic to the network. This process is usually referred to as Network Access Planning. Another well-known aspect is the design of an efficient backbone network for carrying network traffic. This is usually referred to as Network Backbone Planning. The network backbone may serve a metropolitan area or a larger geographical area.
There are also many performance issues related to ATM network planning, such as network survivability, qualities of service (QoS) and grades of service (GoS). Since all of these factors are interrelated in quite a complex manner, network planning is a complicated process. In order to facilitate the process, computerized tools have been invented to find optimal network design solutions given traffic demand and access switch locations. One such tool is taught in U.S. Pat. No. 5,508,999 which issued on Apr. 16, 1996 to Cox, Jr. et al. This patent teaches a method and system for generating an optimized transition plan for the placement and interconnection of carrier hubs in a local access network. Cox Jr. et al. use a mixed-integer programming for finding an optimal access network design.
The shortcomings of integer programming for use in network design are well known. Although such programming will find the optimal design, the time required to find the optimal solution is generally unacceptable for all but relatively small networks. In fact, for medium and large sized networks, the time involved in finding the optimal solution becomes prohibitive.
There therefore exists a need for a network planning method which is capable of finding an optimal or a near-optimal solution to a network design problem in a reasonable time. There also exists a need for a network planning method which is capable of finding an optimal lowest cost design solution for medium and large sized networks.